 // init!! , G is root , B is base , len = 2^x
namespace NTT {
    const int N = (1<<19) , P = (479 << 21) + 1, G = 3 , B = 2;
    int w[2][N],rev[N];
    ll Pow(ll x, ll t){ll r=1;for(;t;t>>=1,x=x*x%P)if(t&1)r=r*x%P;return r;}
    void ini(){
        ll t = Pow(G,(P-1)/N);
        w[0][0] = w[1][0] = 1;
        rep(i,1,N) w[0][i] = t*w[0][i-1]%P;
        rep(i,1,N) w[1][i] = w[0][N-i];
        rep(i,0,N) for(int j=1;j<N;j*=B) (rev[i]<<=1)|=(i/j)%B;
    }
    void ntt(int *a,int n,int o){
        int tt = N/n;
        rep(i,0,n){
            int j = rev[i]/tt;
            if(i<j) swap(a[i],a[j]);
        }
        for(int i=1;i<n;i<<=1)
            for(int j=0,t=N/(i+i);j<n;j+=i+i)
                for(int k=j,l=0;k<j+i;++k,l+=t){
                    int b = (ll)a[k+i]*w[o][l]%P;
                    a[k+i] = a[k]-b; if(a[k+i]<0) a[k+i]+=P;
                    a[k] = a[k]+b; if(a[k]>=P) a[k]-=P;
                }
        if(o == 1){
            ll inv = Pow(n,P-2);
            rep(i,0,n) a[i] = a[i]*inv%P;
        }
    }
    void mult(int *a,int *b,int len){
        ntt(a,len,0);ntt(b,len,0);
        rep(i,0,len) a[i] = (ll)a[i]*b[i]%P;
        ntt(a,len,1);
    }
}
